The present invention relates to industrial controllers for controlling industrial processes and equipment and more generally to an operating system suitable for a distributed industrial control system having multiple processing nodes spatially separated about a factory or the like.
Industrial controllers are special purpose computers used for controlling industrial processes and manufacturing equipment. Under the direction of a stored control program the industrial controller examines a series of inputs reflecting the status of the controlled process and in response, adjusts a series of outputs controlling the industrial process. The inputs and outputs may be binary, that is on or off, or analog providing a value within a continuous range of values.
Centralized industrial controllers may receive electrical inputs from the controlled process through remote input/output (I/O) modules communicating with the industrial controller over a high-speed communication network. Outputs generated by the industrial controller are likewise transmitted over the network to the I/O circuits to be communicated to the controlled equipment. The network provides a simplified means of communicating signals over a factory environment without multiple wires and the attendant cost of installation.
Effective real-time control is provided by executing the control program repeatedly in high speed xe2x80x9cscanxe2x80x9d cycles. During each scan cycle each input is read and new outputs are computed. Together with the high-speed communications network, this ensures the response of the control program to changes in the inputs and its generation of outputs will be rapid. All information is dealt with centrally by a well-characterized processor and communicated over a known communication network to yield predictable delay times critical to deterministic control.
The centralized industrial controller architecture, however, is not readily scalable, and with foreseeably large and complex control problems, unacceptable delays will result from the large amount of data that must be communicated to a central location and from the demands placed on the centralized processor. For this reason, it may be desirable to adopt a distributed control architecture in which multiple processors perform portions of the control program at spatially separate locations about the factory. By distributing the control, multiple processors may be brought to bear on the control problem reducing the burden on any individual processor and the amount of input and output data that must be transmitted.
Unfortunately, the distributed control model is not as well characterized as far as guaranteeing performance as is required for real-time control. Delay in the execution of a portion of the control program by one processor can be fatal to successful real-time execution of the control program, and because the demand for individual processor resources fluctuates, the potential for an unexpected overloading of a single processor is possible. This is particularly true when a number of different and independent application programs are executed on the distributed controller and where the application programs compete for the same set of physical hardware resources.
One weak point in the distributed control model is the introduction of communication delays in the execution of control tasks. These communication delays result from the need for different portions of the control program on different spatially separated hardware to communicate with each other. In a typical first-in/first-out (FIFO) communication system, where outbound messages are queued according to their time of arrival at the communication circuit, a message with a high priority, as may be necessary for the prompt completion of a control task, will always be transmitted later than an earlier arriving message of low priority. This can cause a form of unbounded priority inversion where low priority task block high priority tasks, and this may upset the timing requirements of the real-time control program.
A second problem with the distributed control model arises from operating distributed control devices in a multi-tasking mode to be shared among different program tasks. Such multi-tasking is necessary for efficient use of hardware resources. Present real-time multitasking operating systems allow the assignment of a priority to a given task. The user selects the necessary priority levels for each task to ensure that the timing constraints implicit in the real-time control process are realized.
One problem with this approach is first that it is necessarily conservative because the priorities must be set before the fact resulting in poor utilization of the scheduled resource. Further because the timing constraints are not explicit but only indirectly reflected in the priorities set by the user, the operating system is unable to detect a failure to meet the timing constraints during run time.
On the other hand, some dynamic scheduling systems (which adapt to the circumstances at run-time) exist but they don""t accept user assigned priorities and thus provide no guarantee as to which tasks will fail under transient overload conditions. There are also scheduling systems for multi-tasking that allow for both setting of priorities and that have a dynamic component to allow for greater processor utilization, for example, those that use the Maximum Urgency First algorithm. See generally D. B. Stewart and P. K. Khosla, xe2x80x9cReal Time Scheduling of Dynamically Reconfigurable Systems,xe2x80x9d Proceedings of the 1991 International Conference on Systems Engineering, Dayton August 1991 pp. 139-142.
Unfortunately, such algorithms require rescheduling of all tasks as a new task becomes ready for execution. This results in greater overhead and produces a potential for an unbounded number of context switches (in which the scheduled resource switches its task) which can be detrimental to guaranteeing a completion time for a particular task as required by real-time control. Further current scheduling systems do not provide any guarantee for execution time of the tasks and the potential allow low priority tasks to fail.
The present invention provides an operating system for a distributed control system that applies more sophisticated scheduling to the queuing of messages intercommunicating between distributed tasks. By investing the communication circuitry with an appropriate scheduling system, guarantees may be made for the completion of distributed tasks of which communication between the distributed tasks is a part.
The scheduling used in the preferred embodiment considers both the priority of the message and an allocated portion of a timing constraint imposed on the message by the operating system, that timing constraint portion being a fraction of the timing guarantee for the task of which the message is a part. Messages are only transmitted if bandwidth for the message has been pre-allocated by the operating system.
The mixed priority scheduling system for messages may also be used more generally in scheduling tasks for the processor in a multi-tasking environment.
Specifically then, the present invention provides a distributed control system having a network and a set of spatially distributed control components attached to the network, each including a processor and a memory system as well as a portion of an application distributed over these multiple control components. A communication circuit connects the control component to the network allowing intercommunication via messages with other control components having other portions of the application program. The operating system provides a time constraint value for the execution of the portion of an application program at a given control component and the communication circuit responds to the time constraint value to queue the message to meet the time constraint value.
Thus it is one object of the invention to produce a communication circuit that is sensitive to timing considerations inherent in the execution of tasks for real-time control over multiple, spatially separated control components. By allowing the queuing of messages to conform to the time constraints of the messages, guarantees may be had as to when an overall control task will be completed where the control task includes both processing and communication.
The communication circuit may include a message queue having locations for storing messages (the locations determining an order for transmission of the messages on the network). A message scheduler operates to receive new messages together with a pre-identified priority and a completion timing constraint for the message and to insert the new message in the message queue at a location that is a function of both the priority and the completion timing constraint.
Thus it is another object of the invention to provide a scheduling of the communication circuit that is both dynamically responsive to timing constraints and which is responsive to statically imposed priorities thus allowing both efficient use of resources and the ability to guarantee the execution of critical tasks.
Each new message may be associated with an execution time necessary to transmit the new message on the network and the scheduler may first locate an insertion point of the messages into the queue according to priority and then, if there are multiple messages at the same priority, according to the LATEST STARTING TIME of the new message with respect to other messages in the queue. The LATEST STARTING TIME may equal an arrival time of the new message at the communication circuit plus the completion time constraint minus the execution time for the message. The execution time is how long it is expected the execution (e.g., transmission) of the message will require.
Thus, it is another object of the invention to provide a queuing of messages suitable for real-time control that does not require rescheduling of queued messages as new messages arrive. The LATEST STARTING TIME is fixed upon arrival of the new message and thereafter does not change.
When there are multiple messages with the same priority and LATEST STARTING TIME, the scheduler inserts the new message in a location in the queue according to the completion timing constraint or deadline period of the new message relative to the other messages in the queue.
Thus it is another object of the invention to provide a method of breaking possible ties making use of the fact that shorter deadline periods may indicate relative urgency.
When there are multiple messages for the same priority, the same LATEST STARTING TIME and same completion timing constraint, the scheduler may insert the new message in a location in the queue according to the execution time of the new message relative to other messages in the queue.
Thus it is another object of the invention to provide a tie breaker that enlists the observation that in the case of transient overload, it may be best to execute the task with the shortest execution time first resulting in the maximum number of tasks being executed, all else being equal.
The scheduler will not insert a message into the queue unless the interarrival period of the message (a time indicating how frequently the message is likely to occur) has expired and that the necessary resources needed for processing the message have been previously reserved.
Thus it is another object of the invention to prevent failure of critical tasks by ensuring that all bandwidths for necessary hardware are pre-allocated.
The present scheduling system also may be used for the scheduling of tasks on a processor in a multi-processing environment where the tasks are queued instead of messages.
Thus it is another object of the invention to provide a general purpose mixed priority system that when used with pre-allocation of hardware resources provides for efficient real-time control with guaranteed completion times of tasks.